package com.base.weeks.weeksof270th;

/**
 * TODO
 *
 * @author leon
 * @date 2021年12月05日 11:20
 */
public class GetDirections {
    StringBuilder rootToStart = new StringBuilder();
    StringBuilder rootToDest = new StringBuilder();
    int s;
    int d;

    public String getDirections(TreeNode root, int startValue, int destValue) {
        s = startValue;
        d = destValue;

        dfs(root,startValue,new StringBuilder());
        dfs(root,destValue,new StringBuilder());

        int n = Math.min(rootToStart.length(),rootToDest.length());


        for (int i = 0; i < n; i++) {
            if(rootToStart.charAt(0)!=rootToDest.charAt(0)){
                break;
            }else{
                // 删除比较头一个元素，并且删除头一个元素，
                rootToStart.deleteCharAt(0);
                rootToDest.deleteCharAt(0);
            }
        }

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < rootToStart.length(); i++) {
            res.append('U');
        }
        res.append(rootToDest);
        return res.toString();
    }

    public void dfs(TreeNode root, int destValue, StringBuilder builder) {
        if (root.val == s&&root.val==destValue) {
            rootToStart.append(builder.toString());
        }else if (root.val==d&&root.val==destValue){
            rootToDest.append(builder.toString());
        }

        if (root.left != null) {
            builder.append('L');
            dfs(root.left, destValue, builder);
            builder.deleteCharAt(builder.length() - 1);
        }

        if (root.right != null) {
            builder.append('R');
            dfs(root.right, destValue, builder);
            builder.deleteCharAt(builder.length() - 1);
        }


    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
